/*
 * @lc app=leetcode.cn id=44 lang=cpp
 * @lcpr version=30204
 *
 * [44] 通配符匹配
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();
        
        // dp[i][j] 表示 s 的前 i 个字符与 p 的前 j 个字符是否匹配
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        
        // 空字符串匹配空模式
        dp[0][0] = true;
        
        // 处理模式 p 以 * 开头的情况（* 可以匹配空字符串）
        for (int j = 1; j <= n; ++j) {
            if (p[j - 1] == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }
        
        // 填充 dp 表
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    // * 可以匹配空（dp[i][j-1]）或多个字符（dp[i-1][j]）
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } 
                else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
                    // ? 匹配任意单个字符，或字符直接匹配
                    dp[i][j] = dp[i - 1][j - 1];
                } 
                else {
                    // 字符不匹配且不是通配符
                    dp[i][j] = false;
                }
            }
        }
        
        return dp[m][n];
    }
};
// @lc code=end



/*
// @lcpr case=start
// "aa"\n"a"\n
// @lcpr case=end

// @lcpr case=start
// "aa"\n"*"\n
// @lcpr case=end

// @lcpr case=start
// "cb"\n"?a"\n
// @lcpr case=end

 */

